import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class P51 {
	private static void permutation(List<String> list, String text, String result) {
		
		if (text.length() == 0) {
			list.add(result);
			return;
		}
		
		for (int i = 0; i < text.length(); i++) {
			permutation(list, text.substring(0, i) + text.substring(i + 1), result + text.charAt(i));
		}		
	}
	
	private static List<String> permutation(String text) {
		List<String> list = new ArrayList<String>();
		permutation(list, text, "");
		return new ArrayList<String>(new HashSet<String>(list));
	}
	
	private static boolean isPrime(int n) {
		if (n < 2) {
			return false;
		}

		int max = (int) Math.sqrt(n);
		for (int i = 2; i <= max; i++) {
			if (n % i == 0) {
				return false;
			}
		}

		return true;
	}
	
	private static Map<Integer, Integer> getSameDigit(int n) {
		String num = String.valueOf(n);
		Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();

		for (int i = 0; i < num.length(); i++) {
			String x = num.substring(i, i + 1);
			Integer count = countMap.get(x);
			if (count == null) {
				count = 0;
			}
			countMap.put(Integer.parseInt(x), ++count);
		}

		Iterator<Integer> iterator = countMap.keySet().iterator();
		while (iterator.hasNext()) {
			Integer x = iterator.next();
			if (countMap.get(x) == 1) {
				countMap.remove(x);
			}
		}

		return countMap;
	}

	public static boolean isMatched(int n, String x) {
		String num = String.valueOf(n);
		
		if (num.length() < x.length()) {
			return false;
		}
		
		boolean isMatched = true;
		for (int i = 0; i < x.length(); i++) {
			String t = x.substring(i, i + 1);
			if (!t.equals(" ")) {
				if (!t.equals(num.substring(i, i + 1))) {
					isMatched = false;
				}
			}
		}

		return isMatched;
	}

	public static void main1(String[] args) {
		System.out.println(isMatched(12322, " 2 2 "));
		
		List<String> list = permutation("0012");
		for (String string : list) {
			System.out.println(string);
		}
	}
	
	public static void main(String[] args) {	
		List<Integer> primeList = new ArrayList<Integer>();
		Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();
		
		for (int position = 2; true; position++) {
			int x = (int) Math.pow(10, position - 1);
			int y = (int) Math.pow(10, position);
			
			for (int n = x; n < y; n++) {
				if (isPrime(n)) {
					primeList.add(n);
				}
			}
			
			for (int sameDigitCount = 1; sameDigitCount <= position; sameDigitCount++) {
				for (int digit = 0; digit <=9; digit++) {
					StringBuffer p = new StringBuffer();
					for (int count = 1; count <= position; count++) {
						if (count <= sameDigitCount) {
							p.append(digit);
						} else {
							p.append(" ");
						}
					}
					
					List<String> permutation = permutation(p.toString());
					
					for (String text : permutation) {
						System.out.println(text);
						try {
						//	Thread.sleep(1000);
						} catch (Exception e) {
							// TODO: handle exception
						}
						
						
						
						for(Integer n : primeList) {
							if (isMatched(n, text)) {	
								System.out.println(">>>" + n);
								StringBuffer key = new StringBuffer(String.valueOf(n));
								for (int c = 0; c < text.length(); c++) {
									if (text.charAt(c) != ' ') {
										key.setCharAt(c, '*');
									} 
								}								
								
								System.out.println(">>>key" + key.toString());
								List<Integer> familyList = map.get(key.toString());
								if (familyList == null) {
									familyList = new ArrayList<Integer>();
									map.put(key.toString(), familyList);
								}
								
								if (!familyList.contains(n)) {
									familyList.add(n);
								}
							}
						}				
					}
				}
			}
			
			Iterator<String> iterator = map.keySet().iterator();
			while (iterator.hasNext()) {
				String key = iterator.next();
				
				List<Integer> family = map.get(key);
				System.out.println(key + ":" + family.size());
				if (family.size() == 8) {
					System.out.println(family);
					return;
				}
			}
		}
	}
	
	
	public static void main2(String[] args) {	
		List<Integer> list = new ArrayList<Integer>();

		for (int i = 10000; i <= 99999; i++) {
			if (isPrime(i)) {
				list.add(i);
			}
		}

		Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();
		
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if (i != j) {
					for (int k = 0; k <= 9; k++) {
						StringBuffer x = new StringBuffer();
						x.append("     ");
						x.setCharAt(i, String.valueOf(k).charAt(0));
						x.setCharAt(j, String.valueOf(k).charAt(0));
						
						//System.out.println(x.toString());
						
						
						for(Integer n : list) {
							if (isMatched(n, x.toString())) {								
								StringBuffer key = new StringBuffer(String.valueOf(n));
								key.setCharAt(i, '*');
								key.setCharAt(j, '*');
								

								//System.out.println(key + ":" + n);
								
								List<Integer> familyList = map.get(key.toString());
//								if ("56**3".equals(key.toString())) {
//									System.out.println("@" + n);
//									System.out.println("@" + familyList);
//								}
								if (familyList == null) {
									familyList = new ArrayList<Integer>();
									map.put(key.toString(), familyList);
								}
								
								if (!familyList.contains(n)) {
									familyList.add(n);
								}
							}
						}						
						
						try {
						//	Thread.sleep(1000);	
						} catch (Exception e) {
							// TODO: handle exception
						}
						
					}
					
					
				}
			}
		}
		
		Iterator<String> iterator = map.keySet().iterator();
		while (iterator.hasNext()) {
			String key = iterator.next();
			
			List<Integer> family = map.get(key);
			System.out.println(key + ":" + family.size());
			if (family.size() == 7) {
				System.out.println(family);
				break;
			}
		}
	}
}
